genetischer Algorithmus

genetischer Algorithmus,

 

Algorithmus, der Strategien aus der Evolutionstheorie nachahmt, um zu einem Optimierungsproblem eine möglichst gute Lösung zu finden. Dabei werden Lösungen eines Problems als Chromosomen dargestellt, nämlich jeweils als Folge elementarer Bausteine, der Gene. Eine Menge solcher Lösungschromosomen heißt Population. Ausgehend von einer Anfangspopulation von vorläufigen (nicht optimalen) Lösungen werden durch Vererbungsmechanismen neue Chromosomen erzeugt, bewertet und einem Selektionsprozess unterworfen, der die besten bereits vorliegenden Lösungen bevorzugt. Im Laufe zahlreicher Wiederholungen der Vererbungsprozesse setzen sich neue, optimierte Lösungen durch (»Survival of the Fittest«, »Überleben der Bestangepassten«).

 

Ein genetischer Algorithmus beruht auf folgenden prinzipiellen Vererbungsmechanismen:

 

Crossover: Zwei Chromosomen werden geteilt und über Kreuz zu zwei neuen Chromosomen zusammengefügt. Das Crossover kombiniert also bisherige Lösungsteile neu.

 

Mutation: Ein oder mehrere Gene eines Chromosoms werden bei der Vererbung zufällig abgeändert. Dadurch entstehen neue, bisher nicht aufgetretene Lösungselemente.

 

Selektion: Eine Bewertungsfunktion (Fitnessfunktion) beurteilt die Qualität eines Chromosoms.

 

Reproduktion: Ein Chromosom wird unverändert an die nächste Population vererbt. Die Wahrscheinlichkeit der Reproduktion hängt von der vorherigen Bewertung ab. Gute Lösungen überleben mit höherer Wahrscheinlichkeit als schlechte.

 

Bei der Realisierung eines genetischen Algorithmus muss darauf geachtet werden, dass die verschiedenen Vererbungsmechanismen ausgewogen aufeinander abgestimmt sind und nicht etwa ein einzelner Mechanismus dominiert. Stets müssen genügend viele Chromosomen und eine große Anzahl von Lösungsvarianten (genetischer Pool) vorhanden sein.

 

Es gibt sehr viele Varianten von genetischen Algorithmen. Zum Teil werden zusätzliche Vererbungsmechanismen eingesetzt, z. T. gewichtet man diese recht unterschiedlich. In der ursprünglichsten Form bestehen die Chromosomen aus einer Folge von Nullen und Einsen. Heute sind auch die reellen Zahlen als Chromosomeneinträge gebräuchlich.

 

Genetische Algorithmen eignen sich zur effizienten Bearbeitung vieler komplizierter Optimierungsaufgaben, die nicht durch systematisches Durchforschen aller Lösungsmöglichkeiten angegangen werden können wie etwa das Handlungsreisendenproblem. Die besten gefundenen Lösungen sind nicht notwendig optimal, sie liegen aber in der Praxis genügend nahe am Optimum. Die Schwierigkeit in der Anwendung von genetischen Algorithmen liegt hauptsächlich in der Formulierung eines Problems als Chromosom(en). Bisher sind keine Techniken bekannt, wie zu einem Problem eine möglichst gute Kodierung gefunden werden kann.

 

Einen direkten Ansatz, genetische Algorithmen auszunutzen, stellen die DNA-Computer dar.